/**33. 搜索旋转排序数组
 * - 二分查找升级版  
 */
export function searchRotateArray(nums: number[], target: number): number {
    //思路：二分取中点的时候，分为两个区间，其中一个是升序，另一个是乱序 （因为乱序的区间，是旋转点所在的位置）
    if (!nums.length) return -1
    let left = 0, right = nums.length - 1
    while (left <= right) {
        const mid = left + ((right - left) >> 1)
        if (nums[mid] === target) {
            return mid
        }
        // 原本是升序数组，如果mid正常的比left大，说明左边是正常的升序，右边是乱序
        if (nums[mid] >= nums[left]) {
            //进入这个区间进行查找
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        // 原本是升序数组，如果mid比left小了，说明右边是正常的升序，左边是乱序
        else {
            //进入这个区间进行查找
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}
/**704.二分查找
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 */
export function search(nums: number[], target: number): number {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
        const mid = left + ((right - left) >> 1)
        if (nums[mid] > target) {
            right = mid - 1
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}
/**56. 合并区间
 * - 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
export function merge(intervals: number[][]) {
    const res: number[][] = []
    intervals.sort((a, b) => a[0] - b[0])
    let [left, right] = intervals[0]
    for (let i = 1; i < intervals.length; i++) {
        const [nowLeft, nowRight] = intervals[i];
        if (right < nowLeft) {//right比当前的左边界还小，说明没重叠 
            res.push([left, right])
            left = nowLeft //更新左边界
        }
        right = Math.max(right, nowRight)//更新右边界
    }
    res.push([left, Math.max(intervals[intervals.length - 1][1], right)]) //最后再多放一次
    return res
}
/**54. 螺旋矩阵
 * - 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 */
export function spiralOrder(matrix: number[][]): number[] {

    const res: number[] = [];

    let startX = 0, //起始x坐标
        startY = 0, //起始y坐标
        width = matrix[0].length, //水平长度
        height = matrix.length, //竖直长度
        loop = Math.floor(Math.max(width, height) / 2), //向下取整，算出需要绕的圈数（长度最长的边来计算圈数）
        offectX = 1, //水平层的循环边界
        offectY = 1; //竖直层的循环边界


    while (loop--) {
        let row = startX, //行
            col = startY; //列

        //遍历上面那层 从左到右 （列在动）
        for (; col < width - offectX; col++) {
            res.push(matrix[row][col]);
            if (res.length >= width * height) {
                break;
            }
        }
        if (res.length >= width * height) {//边界判断。判断了八个地方（每个循环内和每个循环后），可能可以优化
            break;
        }
        //遍历右边那层 从上到下 （行在动）
        for (; row < height - offectY; row++) {
            res.push(matrix[row][col]);
            if (res.length >= width * height) {
                break;
            }
        }
        if (res.length >= width * height) {
            break;
        }
        //遍历下边那层 从右到左 （列在动）
        for (; col > startX; col--) {
            res.push(matrix[row][col]);
            if (res.length >= width * height) {
                break;
            }
        }
        if (res.length >= width * height) {
            break;
        }
        //遍历左边那层 从下到上 （行在动）
        for (; row > startY; row--) {
            res.push(matrix[row][col]);
            if (res.length >= width * height) {
                break;
            }
        }
        if (res.length >= width * height) {
            break;
        }
        //更新XY的起止位置
        startX++;
        startY++;
        //更新边界
        offectX++;
        offectY++;
    }

    if (width === height && width % 2 === 1) {
        const mid = Math.floor(width / 2);
        res.push(matrix[mid][mid]);
    }
    return res;
}
/**88. 合并两个有序数组
 * - 在nums1的基础上修改原数组
 */
export function mergeSortArray(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1
    let j = n - 1
    /**需要填充的索引 */
    let k = m + n - 1
    //倒序遍历，把大的放最后面
    while (i >= 0 && j >= 0) {
        if (nums1[i] <= nums2[j]) {//2比较大 
            nums1[k] = nums2[j]
            k--; j--;
        } else {//1比较大
            nums1[k] = nums1[i];
            k--; i--;
        }
    }
    while (j >= 0) {//如果i已经结束了，j还没结束
        nums1[k] = nums2[j];
        k--; j--;
    }
};

/**215. 数组中的第K个最大元素
 * - 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * - 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */
export function findKthLargest(nums: number[], k: number): number {
    // On解法：
    const arr = new Array(20001).fill(0); //这里给出2w空间, 也可以不先给空间，后续再赋值
    for (let i = 0; i < nums.length; i++) {
        arr[nums[i] + 10000]++; // 目标位置赋值，数字越大的越靠后（相同的值会在同一个位置）
    }
    for (let i = 20000; i >= 0; i--) {// 倒序遍历，看看k什么时候能够到达指定的位置
        k = k - arr[i]; // 这里arr[i]代表当前位置有多少个相同数字，减去之后看看是否是我们想要的位置
        if (k <= 0) {
            return i - 10000;
        }
    }
    return 0;


    //排序法，但是题目要求On，而我们的快排做不到这个On； 
    function quick(arr: number[]): number[] {
        if (arr.length <= 1) return arr // 边界千万别忘
        const left = []
        const right = []
        const index = Math.floor(Math.random() * arr.length)
        const flag = arr[index]
        for (let i = 0; i < arr.length; i++) {
            if (i !== index) {
                const item = arr[i];
                if (item > flag) {
                    right.push(item)
                } else {
                    left.push(item)
                }
            }
        }
        return quick(right).concat(flag, quick(left)) // 因为需要倒序，所以这里拼接反过来
    }
    return quick(nums)[k - 1]
};